//
// Created by xili on 2024/8/24 15:54.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    vector<int> successfulPairs(vector<int> &spells, vector<int> &potions, long long success) {
        sort(potions.begin(), potions.end());
        int m = potions.size();
        vector<int> ans;
        for (auto &item: spells) {
            int l = 0, r = m - 1;
            int cnt = 0;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if ((long long) item * potions[mid] >= success) {
                    cnt = max(cnt, m - mid);
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};